//************************************************************
//    > File Name: Qsort.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月 8日 11:47:56
//***********************************************************
//lintcode #464
#include<bits/stdc++.h>
using namespace std;
void Qsort(int a[],int low,int high)
{
	if(low >= high)
		return;
	int first = low;
	int last = high;
	int key = a[low];
	while(first < last)
	{
		while(first < last && a[last]>=key)
			--last;
		a[first]=a[last];
		while(first < last && a[first] <= key)
			++first;
		a[last]=a[first];
	}
	a[first] = key;
	Qsort(a,low,first-1);
	Qsort(a,first+1,high);
}
int main()
{
	int a[]={6,4,8,2,9,3,7,6,1,5,7};
	Qsort(a,0,sizeof(a)/sizeof(a[0])-1);
	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
		cout<< a[i] <<" ";
	cout<<endl;
	return 0;
}
